//
// Description: 139. 单词拆分
// Created by Loading on 2022/6/26.
//

#include <bits/stdc++.h>

using namespace std;

bool wordBreak(string s, vector<string> &wordDict) {
    int n = s.size();
    unordered_set<string> hash(wordDict.begin(), wordDict.end());

    // dp[i] 表示能否拼出 s 的前 i 个字符
    bool dp[n + 1];
    memset(dp, false, sizeof dp);
    dp[0] = true;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            // 记忆化搜索
            if (dp[j] && hash.find(s.substr(j, i - j)) != hash.end()) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}

int main() {
    string s = "catsandog";
    vector<string> wordDict{"cats", "dog", "sand", "and", "cat"};

    auto res = wordBreak(s, wordDict);

    cout << res << endl;

    return 0;
}
